1. Field of the Invention
The present invention relates generally to a forward error correction apparatus and method in a digital communication system, and in particular, to a forward error correction apparatus and method in a digital communication system for high-speed data transmission.
2. Description of the Related Art
Generally, in a digital communication system, errors occur due to the noise generated in a transmission link, and various error correction techniques are used to correct the errors. In a wireless communication system adopting the 3GPP (3rd Generation Partnership Project) or 3GPP2 (3rd Generation Partnership Project 2) standard, use of a convolutional code has been proposed for transmission of voice and control signals, and use of a turbo code has been proposed for effective transmission of high-speed data. Of the codes stated above, the turbo code for transmission of high-speed data is advantageous in that it has a very low bit error rate (BER) at a low signal-to-noise ratio (SNR). However, the turbo code has several shortcomings in terms of its performance and implementation, discussed below.
First, the turbo code has a relatively short minimum distance. Therefore, during decoding of a signal coded with the turbo code, an error floor phenomenon may occur at a desired bit error rate. In addition, undetected error probability for a codeword in which an error has occurred during decoding is relatively high.
Second, in the decoding process of the turbo code, efficient decoding stop is needed to reduce decoding time and power consumption during the decoding process. Therefore, in order to provide an efficient decoding stop, a CRC (Cyclic Redundancy Code) check process for error detection at each iterative decoding, or an additional algorithm for the decoding stop is required.
Third, an algorithm for decoding the turbo code cannot be realized in a parallel architecture, so there are limitations in increasing the decoding rate.
Recently, a low density parity check code (hereinafter referred to as “LDPC code”) has attracted public attention as a code that is similar or superior to the turbo code in performance, and can resolve the above problems. The LDPC code has a very small number of ‘1’s in each row and column of a parity check matrix defining a code, and its structure can be defined by a factor graph consisting of a check node, a variable node, and an edge connecting the nodes. The LDPC code has a longer minimum distance than a turbo code with the same length. Therefore, it is generally known by those skilled in the art that in the LDPC code, compared with the turbo code, an error floor occurs at a very low bit error rate and the undetected error probability for a defective codeword is very low; experimentally, it has been shown to be close to zero. In addition, the LDPC can be implemented in a parallel architecture, contributing to a drastic reduction in decoding time, and can enable efficient decoding stop through parity check performed at each iterative decoding without some overhead, such as an additionally added CRC or a decoding stop algorithm.
The decoding process of the LDPC code is performed by iterative decoding based on a “sum-product” algorithm. An optimum sum-product algorithm includes a somewhat complicated arithmetic expression. Therefore, when the sum-product algorithm is used, a large amount of calculation is required in the decoding process. Accordingly, the use of the sum-product algorithm undesirably increases hardware complexity.
Therefore, when the LDPC code is used, there is necessity to further simplify the optimum decoding algorithm in an actual implementation. In order to minimize performance degradation due to the simplified algorithm, a weighting factor is applied to extrinsic information generated in the decoding process.
A detailed description will first be made of the LDPC code. The LDPC code can be defined by a factor graph. The factor graph consists of a check node indicating a parity check expression of a predetermined LDPC code, a variable node indicating each code symbol, and an edge indicating dependency between the nodes. The edge connects each check node to a variable node corresponding to a code symbol included in the parity check expression indicated by the check node. If the number of variable nodes connected to all check nodes is fixed to dc and the number of check nodes connected to all variable nodes is fixed to dv, a corresponding LDPC code is called “regular LDPC code.” In addition, if the number of edges connected to each check node and variable node is not constant, the corresponding LDPC code is referred to as “irregular LDPC code.” Herein, only the regular LDPC code will be considered.
A process of decoding the LDPC code is performed by iterating a process in which a variable node and a check node on a factor graph exchange messages generated and updated for each node. In this case, each node updates a message by using a sum-product algorithm. A sum-product algorithm defined using a log likelihood ratio (hereinafter referred to as “LLR”) for decoding of the LDPC code, and an LDPC code iterative decoding process based on the sum-product algorithm will be described herein below.
First, initialization (j=0) is performed as follows. An initial message of a variable node n is defined as the channel reliability of an nth symbol of a received codeword, and this is shown by
                              q          mn                      (            0            )                          =                              l            n                          (              0              )                                =                      ln            ⁡                          (                                                p                  0                                /                                  p                  1                                            )                                                          Equation        ⁢                                  ⁢                  (          1          )                    
In Equation (1),
  q  mn      (    0    )  is an initial value of an initially defined variable node message, and
  l  n      (    0    )  is an initial LLR value for the initially defined variable node. In addition, P0 and P1 are transmission link transition probabilities for a symbol ‘0’ and a symbol ‘1’, respectively.
After the initialization process, iterative decoding must be carried out. A description will now be made of iterative decoding at jth iteration. At the jth iteration, a check node message is updated (check node message update process). That is, the check node message becomes a message transmitted from a check node n to a variable node n. This can be expressed by
                              r          mn                      (            j            )                          =                  ln          ⁡                      (                                          1                +                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      tanh                    ⁡                                          (                                                                        q                          i                                                      (                            j                            )                                                                          /                        2                                            )                                                                                                  1                -                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                                                          ⁢                                      tanh                    ⁡                                          (                                                                        q                          i                                                      (                            j                            )                                                                          /                        2                                            )                                                                                            )                                              Equation        ⁢                                  ⁢                  (          2          )                    
In Equation (2),
  r  mn      (    j    )  is a value obtained in a jth iterative decoding process in an iterative decoding process, and represents a message transmitted from a check node m to a variable node n. In addition,
  q  i      (    j    )  represents a message transmitted from a variable node i to a check node m in a jth iterative decoding process. Here, i indicates a value determined by rearranging variable nodes connected to a check node m from 0 to dc−1. Therefore, when i=0, it means a variable node n.
When a variable node is updated by Equation (2), the variable node transmits a new message to a check node. The transmitted message becomes a message transmitted from a variable node n to a check node m, and this can be expressed by
                              q          mn                      (                          j              +              1                        )                          =                              q            mn                          (              0              )                                +                                    ∑                              i                =                1                                                              d                  v                                -                1                                      ⁢                                                  ⁢                          r              i                              (                j                )                                                                        Equation        ⁢                                  ⁢                  (          3          )                    
In Equation (3),
  q  mn      (          j      +      1        )  is a value obtained in a jth iterative decoding process, and represents a message transmitted from a variable node n to a check node m. At this point,
  r  i      (    j    )  represents a message transmitted from a check node i to a variable node n in a jth iterative decoding process, and i indicates a value determined by rearranging check nodes connected to a variable node n from 0 to dc−1. Therefore, when i=0, it means a check node m.
After initialization is carried out as illustrated in Equation (1) to Equation (3), the LLR update is performed through a process of exchanging messages between a check node and a variable node after an iterative decoding process. The LLR update is achieved by
                              l          n                      (                          j              +              1                        )                          =                              l            n                          (              0              )                                +                                    ∑                              i                =                1                                                              d                  v                                -                1                                      ⁢                                                  ⁢                          r              i                              (                j                )                                                                        Equation        ⁢                                  ⁢                  (          4          )                    
In Equation (4),
  l  n                    ⁢          (              j        +        1            )      indicates an LLR value defined for a variable node n in a jth iterative decoding process.
After the LLR update is carried out by Equation (4), a decision process is performed. The decision process is achieved according to an LLR update result calculated by Equation (4), and is performed for all code symbols. A method for performing the decision process can be represented byIf ln≧0, {circumflex over (x)}n=0 and else, {circumflex over (x)}n=1  Equation (5)
In Equation (5), ln is an LLR value defined for a variable node n at a particular decoding time. That is, ln is equivalent to
  l  n                    ⁢          (              j        +        1            )      of Equation (4), and {circumflex over (x)}n represent a codeword symbol estimated through a decoding process.
After the decision process is performed as shown by Equation (5), if a decoded codeword satisfies all parity check expressions, iteration is stopped. However, if the decoded codeword fails to satisfy all parity check expressions, the j value is increased by 1 and then, the process of Equation (2) to Equation (5) is iterated. Such iteration can be performed as many times as a predetermined iteration number. Even after the iteration is performed as many times as a predetermined maximum iteration number, if the codeword fails to satisfy all parity check expressions, the decoding is stopped and then, decoding failure is declared.
In the foregoing description, a sum-product algorithm used by each node in the message update process is called “optimum sum-product algorithm.” The optimum sum-product algorithm can be simply derived through a theoretical calculation process without a certain approximation process.
However, the check node message update process shown by Equation (2) can be simplified as shown in Equation (6) below, for approximation.
                                                                                                                                                                                                                  r                            mn                                                          (                              j                              )                                                                                =                                                                                    CHK                              ⁡                                                              (                                                                                                      q                                    1                                                                    ,                                                                      q                                    2                                                                    ,                                                                                                                                          ⁢                                  …                                  ⁢                                                                                                                                          ,                                                                      q                                                                                                                  d                                        c                                                                            -                                      1                                                                                                                                      )                                                                                      =                                                          CHK                              ⁡                                                              (                                                                                                      q                                    1                                                                    ⁢                                                                      CHK                                    ⁡                                                                          (                                                                                                                        q                                          2                                                                                ,                                                                                                                                                                  ⁢                                        …                                        ⁢                                                                                                                                                                  ,                                                                                  q                                                                                                                                    d                                              c                                                                                        -                                            1                                                                                                                                                              )                                                                                                                                      )                                                                                                                                                                                                                                                                                                            CHK                              ⁡                                                              (                                                                                                      q                                    x                                                                    ,                                                                      q                                    y                                                                                                  )                                                                                      =                                                          ln                              ⁡                                                              (                                                                                                      1                                    +                                                                                                                  tanh                                        ⁡                                                                                  (                                                                                                                                    q                                              x                                                                                        /                                            2                                                                                    )                                                                                                                    ⁢                                                                              tanh                                        ⁡                                                                                  (                                                                                                                                    q                                              y                                                                                        /                                            2                                                                                    )                                                                                                                                                                                                                          1                                    -                                                                                                                  tanh                                        ⁡                                                                                  (                                                                                                                                    q                                              x                                                                                        /                                            2                                                                                    )                                                                                                                    ⁢                                                                              tanh                                        ⁡                                                                                  (                                                                                                                                    q                                              y                                                                                        /                                            2                                                                                    )                                                                                                                                                                                                                    )                                                                                                              ⁢                                                                                                                                                                                                                                                                                            ≈                                                                                                    sgn                            (                                                          q                              x                                                        )                                                    ⁢                                                      sgn                            (                                                          q                              y                                                        )                                                    ⁢                                                      min                            ⁡                                                          (                                                                                                |                                                                      q                                    x                                                                    |                                                                ,                                                                  |                                                                      q                                    y                                                                    |                                                                                            )                                                                                                      +                                                  c                          ⁢                                                                                                          ⁢                                                      (                                                          c                              :                                                                                                                          ⁢                                                              correction                                ⁢                                                                                                                                  ⁢                                factor                                                                                      )                                                                                                                ⁢                                                                                                                                                                                        c              =                              {                                                                                                    -                        0.5                                                                                                                                                                  if                            ⁢                                                                                                                  ⁢                                                          (                                                              |                                                                                                      q                                    x                                                                    +                                                                      q                                    y                                                                                                  |                                                                  >                                  2                                                                |                                                                                                      q                                    x                                                                    -                                                                      q                                    y                                                                                                  |                                                            )                                                        ⁢                                                                                                                  ⁢                            and                                                    ⁢                                                                                                          |                                                                                    q                              x                                                        -                                                          q                              y                                                                                |                                                      <                            2                                                                          ⁢                                                                                                                                                                                                  0.5                                                                                                                                            if                            ⁢                                                                                                                  ⁢                                                          (                                                              |                                                                                                      q                                    x                                                                    -                                                                      q                                    y                                                                                                  |                                                                  >                                  2                                                                |                                                                                                      q                                    x                                                                    +                                                                      q                                    y                                                                                                  |                                                            )                                                        ⁢                                                                                                                  ⁢                            and                                                    ⁢                                                                                                          |                                                                                    q                              x                                                        +                                                          q                              y                                                                                |                                                      <                            2                                                                          ⁢                                                                                                                                                                                                  0                                                              otherwise                                                                                                                              Equation        ⁢                                  ⁢                  (          6          )                    
In Equation (6), qx and qy represent variable node messages applied to the check node. In addition, sgn(x) is a function having a value of 1 for x>0 and a value of −1 for x<0.
Equation (6) shows an optimum sum-product algorithm in which a check node message update process is simplified through an approximation process. For a message updated in a particular check node m, signs of variable node messages on two particular edges are multiplied by each other, and then, the result is used as a sign of a temporary result message. In addition, when compared to the absolute values of the variable node messages, a smaller value is selected and defined as a size of the temporary result message. In order to correct an error caused by the approximation process, the temporary result message is updated by adding a correction factor c determined by a predetermined rule to the temporary result message. Further, a check node message is finally updated by iteratively applying such a process to other edges connected to a check node m except the edges connected to a variable node n. A sum-product algorithm using this is called ‘sum-product algorithm with correction factor’. The approximated LDPC code iterative decoding, based on the ‘sum-product algorithm with correction factor’, shows superior performance with regards to the decoding performance that can be obtained by an optimum sum-product algorithm, without performing the somewhat complicated calculation of tanh( ) in a check node message update process in an LDPC code decoding process based on the optimum sum-product algorithm.
The optimum sum-product algorithm, as can be noted from Equation (2), must perform calculation of tanh( ) function for each of check node messages applied to a check node in order to update a check node message at a particular iterative decoding time. This increases complexity during hardware implementation due to the complicated calculation of tanh( ) function. In order to solve these problems, there has been proposed an algorithm for simplifying a check node message update process through an approximation process and applying a correction factor to the approximation process to minimize performance degradation due to the approximation process. However, the ‘sum-product algorithm with correction factor’ must determine a correction factor for all edges connected to a check node according to a variable node message delivered from the edges in order to finally update the check node message. Since such an operation must be performed on all edges in sequence, each check node undesirably requires a relatively large amount of calculation and a long calculation time.